#! /usr/bin/env python

# Alunos:   Eliezer de Souza da Silva  RA: 124065
#           Fernanda Brandao Silva     RA: 060727
#           Michel Silva Fornaciali    RA: 071884
# IA368R: Eduardo Valle - Trabalho 3, Programa 3 - Processamento da consulta

import sys
from operator import itemgetter
from numpy import array, dot, sqrt

def distEuclidiana(v,w):
    # Calcula a distancia euclidiana de dois vetores
    return sqrt(dot(v-w,v-w))
    
def stdin2array(line):
    # Dado uma linha do descritor da imagem, extrai o vetor de caracteristica e converte em array  
    return array(line.split(" ")[4:132], 'int')   # PARAMETRIZAR ESTES INDICES!
    
def getIndexOf(votos, min):  
    # Dado o hash de votos e o indice de um vetor da base, retorna o indice da imagem correspondente deste vetor no hash de votos
    for k in range(len(votos)):
        if (votos[k][2] >= min):
            return k
    return -1

    
# --------- PROGRAMA PRINCIPAL ---------
    
print ">>> Inicio da leitura da imagem de consulta..."        
    
# Armazena os parametros de entrada
baseFile = sys.argv[1]          # arquivo da base
nImages = int(sys.argv[2])      # numero de imagens

# Leitura dos vetores de caracteristica da imagem de consulta
consulta = []
for vector in sys.stdin:
    consulta.append(stdin2array(vector))
    
print "  > Fim da leitura da imagem de consulta!"  
print ">>> Inicio do processamento da base..."  
    
# Leitura do arquivo da base
f = open(baseFile)
lines = f.readlines()
f.close()    
    
# Processa a base armazenando os dados no formato "imagem, vetorCaracteristica" e tambem criando um indice de votos
base = []
votos = []  
primeiroVoto = True
i = -1
for line in lines:        
    aux = line.split(" ")
    base.append([aux[0], array(aux[5:133], 'int')])    # PARAMETRIZAR ESTES INDICES!
    if (primeiroVoto):
        votos.append([aux[0], 0, 0])
        primeiroVoto = False
    elif ((votos[len(votos)-1][0] != aux[0])):
        votos[len(votos)-1][2] = i
        votos.append([aux[0], 0, 0])        
    i = i + 1                
votos[len(votos)-1][2] = i        

print "  > Fim do processamento da base!"  
tBase = len(base)
total = tBase*len(consulta)
print ">>> Inicio da contagem de votos: serao calculadas ", total, " distancias..."    

# Processa os votos  
for c in consulta:
    i = -1
    dist = sys.maxint
    min = 0
    for b in base:    
        i = i + 1       
        x = distEuclidiana(c, b[1])
        if (x < dist):
            min = i
            dist = x   
    index = getIndexOf(votos, min)
    votos[index][1] = votos[index][1] + 1   
    
    total = total - tBase
    print "  > Faltam ", total, " calculos"

print "  > Fim da contagem dos votos!"
print ">>> Impressao dos resultados..."
  
# Ordena as imagens pelo numero de votos 
votos = sorted(votos, key=itemgetter(1), reverse=True)   
    
# Lista as N imagens mais votadas
for k in range(nImages):
    sys.stdout.write(str(votos[k][0]) + " " + str(votos[k][1]) + "\n")